import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Scanner;
import java.util.Set;
import java.util.SortedSet;
import java.util.TreeSet;

/**
 * implements an Adjacency List of a Graph data structure.
 * @author BaoTam
 *
 */
public class AdjacencyList {

	/**
	 * A map of vertices to their Adjacencies and the weight associated with
	 * each edge
	 */
	private Map<Vertex, SortedSet<Pair>> al;
	
	/**
	 * The constructor takes in a String object containing the description of the graph as an edge list.
		For this you should use a Scanner object and the nextInt() method of Scanner.
		The rst integer in the string gives the number of edges, e. There are exactly 3  e integers following
		this. Every 3 integers represents an edge, the rst two of the 3 represent the vertices, the third
		integer represents the weight of the edge between the vertices.
		The following example represents a triangle between the 3 vertices numbered 3, 4, and 5
		"3 3 4 1 4 5 1 5 3 1"
	 * @param edgeList
	 */
	public AdjacencyList(String edgeList) {
		al = new HashMap<Vertex,SortedSet<Pair>>();
		
		if((edgeList == null) || (edgeList.compareTo("") == 0)) {
			return;
		}
		
		
		
		Scanner edgeListScanner = new Scanner(edgeList).useDelimiter("\\D+");
		
		int edgeNum = edgeListScanner.nextInt();
		while((edgeNum > 0) && (edgeListScanner.hasNext())) {
			try {
				Vertex 	vertex1 = new Vertex(edgeListScanner.nextInt());
				Vertex 	vertex2 = new Vertex(edgeListScanner.nextInt());
				int		weight  = edgeListScanner.nextInt();
				
				SortedSet<Pair> vertex1AdjSet = al.get(vertex1);
				if (vertex1AdjSet == null) {
					vertex1AdjSet = new TreeSet<Pair>();
					al.put(vertex1, vertex1AdjSet);
				}
				vertex1AdjSet.add(new Pair(vertex2, weight));
				
				SortedSet<Pair> vertex2AdjSet = al.get(vertex2);
				if (vertex2AdjSet == null) {
					vertex2AdjSet = new TreeSet<Pair>();
					al.put(vertex2, vertex2AdjSet);
				}
				vertex2AdjSet.add(new Pair(vertex1, weight));
				
				edgeNum--;
			}
			catch(Exception e) {}
		}
	}
	
	/**
	 * 
	 * @param v
	 * @return the set of the pairs that are adjacent to the vertex
	 */
	public SortedSet<Pair> getAdjacencies(Vertex v) {
		return al.get(v);
	}
	
	/**
	 * @return a string representation of the adjacency list
	 */
	public String toString() {
		String result = "";
		Set<Vertex> keySet = al.keySet();
		Iterator<Vertex> iterator = keySet.iterator();
		while(iterator.hasNext()) {
			Vertex vertex = iterator.next();
			result += (vertex + "\t-- ");
			SortedSet<Pair> pairSet = getAdjacencies(vertex);
			result += (pairSet);
			result += ("\n");
		}
		return result;
	}
	
	/**
	 * used for debugging
	 * @return the set of vertices 
	 */
	public Set<Vertex> getVertexSet() {
		return al.keySet();
	}
	
	/**
	 * used for debugging
	 * @param args
	 */
	public static void main(String[] args) {
		AdjacencyList adjList = new AdjacencyList("10 1 5 10 1 7 7 5 3 3 7 3 6 5 2 2 7 4 11 3 2 15 3 4 20 2 6 9 4 6 14");
		System.out.println(adjList);
		System.out.println("EXPLORE: " + GraphSearch.explore(new Vertex(3), adjList, new MyPrimStructure()));
		System.out.println("SEARCH: " + GraphSearch.search(new Vertex(1), new Vertex(5), adjList, new MyPrimStructure()));
		System.out.println(adjList.getAdjacencies(new Vertex(9)));
	}
	
	
	// used for grading
	
	public void setAl(Map<Vertex, SortedSet<Pair>> al) {
		this.al = al;
	}
	
	
}
